#include <iostream>
#include <cmath>
using namespace std;

const int MAX_SIZE = 100;
// 用于表示棋盘，初始化为全0
int chessBoard[MAX_SIZE][MAX_SIZE];
int solutionCount = 0;

bool isSafe(int row, int col, int n)
{
    // 检查同一列
    for (int i = 0; i < row; i++)
    {
        if (chessBoard[i][col] == 1)
            return false;
    }

    // 检查左上方斜线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
    {
        if (chessBoard[i][j] == 1)
            return false;
    }

    // 检查右上方斜线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
    {
        if (chessBoard[i][j] == 1)
            return false;
    }

    return true;
}

// 递归放置皇后，尝试找到所有解
void placeQueens(int row, int n)
{
    if (row == n)
    {
        solutionCount++;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout << chessBoard[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        return;
    }

    for (int col = 0; col < n; col++)
    {
        if (isSafe(row, col, n))
        {
            chessBoard[row][col] = 1;
            placeQueens(row + 1, n);
            chessBoard[row][col] = 0;
        }
    }
}

int main()
{
    int n;
    cout << "请输入皇后个数n: ";
    cin >> n;
    placeQueens(0, n);
    cout << "总共有 " << solutionCount << " 种放置方案" << endl;
    return 0;
}